package com.cyl.wms.path;

import java.util.Arrays;

public class DijkstraAlgorithm {
    private int[][] graph;
    private int[] dist;
    private boolean[] visited;
    private int start;

    public DijkstraAlgorithm(int[][] graph, int start) {
        this.graph = graph;
        this.start = start;
        this.dist = new int[graph.length];
        Arrays.fill(this.dist, Integer.MAX_VALUE);
        this.visited = new boolean[graph.length];
    }

    public void run() {
        dist[start] = 0;

        for (int i = 0; i < graph.length - 1; i++) {
            int minVertex = getMinVertex();
            visited[minVertex] = true;

            for (int j = 0; j < graph.length; j++) {
                if (graph[minVertex][j] != 0 && !visited[j]) {
                    int newDist = dist[minVertex] + graph[minVertex][j];
                    if (newDist < dist[j]) {
                        dist[j] = newDist;
                    }
                }
            }
        }
    }

    private int getMinVertex() {
        int minDist = Integer.MAX_VALUE;
        int minVertex = -1;
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minVertex = i;
            }
        }
        return minVertex;
    }

    public int[] getShortestDistances() {
        return dist;
    }
}
